The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We study the semantics of a simple language with concurrency and recursion. Our semantic domain consists of (sets of) finite and infinite partially ordered multisets (pomsets) in order to model true concurrency (i.e. non-interleaved parallel execution). It will be shown that the set of pomsets can be turned into a complete ultra-metric space. With the induced notion of convergence, it is possible...
We present solutions to two classical problems concerning distributed systems in which some sites or processes can possibly have byzantine faulty behavior. We first study the naming problem (how to give each site of a network an unique identifier). We are naturally led to make some supplementary assumptions about the synchrony of message passing, the connectivity of the underlying graph and...
We propose an abstract approach towards the fundamental concepts involved in SIMD architectures. Its specificity is to proceed by studying the abstract semantics of parallel languages designed to control those architectures in their various aspects. In this paper, we concentrate on the duality between the macroscopic view of SIMD architectures (a sequential processor operating on array variables),...
By Fidge and Mattern's algorithm, it was already known that it is sufficient to use n-tuple as timestamps of events for a system distributed over n processes if causal independence is to be characterized. In this paper we have shown that smaller clocks do not work if we just know the number of processes. Then using theorems about the dimension of partially ordered sets we have given a mathematical...
This paper is a tutorial introduction to a general methodology, consisting of categorical constructions, for the definition of new algebraic semantics for transition-based formalisms. The methodology individuates three levels of semantic description: programs, structured transition systems, and models. The various formalisms differ for the structure on states and transitions, with respect to which...
This paper surveys some computability aspects in structural operational specifications, fairness concepts and testing equivalences, with special emphasis on infinite behaviours.
Causal Trees are a variant of Milner's Synchronization Trees with enriched action labels which supply indication of the observable causes of observable actions, thus providing us with an interleaving description of concurrent systems which faithfully expresses causality. This model borrows from the interleaving models most of their mathematical simplicity and enhances their descriptive power. Actually,...
Trace languages are used in computer science to provide a description of the behaviours of concurrent systems. If we are interested in systems which never stop then we have to consider languages of infinite traces. In this paper, we generalize to infinite traces three well known points of view about finite traces: equivalence class of words, projections on the dependence cliques and dependence graphs...
We investigate equivalence notions for concurrent systems. We consider “linear time” approaches where the system behaviour is characterised as the set of possible runs as well as “branching time” approaches where the conflict structure of systems is taken into account. We show that the usual interleaving equivalences, and also the equivalences based on steps (multisets of concurrently executed actions)...
In the usual semantics of CCS-like languages, parallelism is reduced to non-deterministic interleaving of actions. As an alternative semantic model for CCS with a clear distinction between concurrency and nondeterminism, Petri nets may be used. This paper gives an introduction to Petri net semantics for CCS. Two approaches are considered: a compositional approach where semantic operations are defined...
This paper recalls some fixpoint theorems in ordered algebraic structures and surveys some ways in which these theorems are applied in computer science. It also points out the shortcomings of the classical least fixpoint theory for domains such as nondeterministic or parallel programs, and shows how to overcome these liabilities by introducing better and more refined fixpoint tools.
The aim of this paper is to introduce an enriched categorical approach which provides a unifying theory for many notions of parallelism and concurrency. Our constructions are based on a concept of observational equivalence induced by a set of observers, which perform experiments over agents. The outcome of those experiments is a set of computations together with an agreement information. In order...
A temporal logic based on actions rather than on states is presented and interpreted over labelled transition systems. It is proved that it has essentially the same power as CTL*, a temporal logic interpreted over Kripke structures. The relationship between the two logics is established by introducing two mappings from Kripke structures to labelled transition systems and viceversa and two transformation...
In this lecture I present some results of Philippe Darondeau, Doris Nolte, Serge Yoccoz and me on the connection of fairness, II30-sets and ultra metrics.
This paper may be seen as proposing a tentative synthesis of various models of parallelism : we establish representation results for three kinds of Models for Distributed Systems, Labelled Transition Systems, Labelled Event Structures and Distributed Languages. For that purpose, we introduce a new representation model for concurrent systems, the Distributed Languages. Based on Words and Equivalence...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.